РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Цель работы

  1. Ознакомиться с принципами составления оценочных характеристик для задач линейного программирования.
  2. Научиться применять симплекс-метода для решения задач линейного программирования.
  3. Изучить табличную форму применения симплекс-метода.
  4. Объяснить различия получаемых результатов.

 

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Обычная задача линейного программирования состоит из трех частей:

целевой функции (на максимум или минимум) – формула (1.1),

основных ограничений– формула (1.2),

ограничений не отрицательности переменных (есть или нет) - формула (1.3)

(1.1)

 

 

 

 

i = 1,… m (1.2)

 

 

(1.3)

Чтобы решить задачу линейного программирования, необходимо привести ее к каноническому виду , когда целевая функция стремится к максимуму. Если целевая функция стремится к минимуму, то необходимо умножить ее на -1.

Основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждого такого k-го неравенства добавить искусственную переменную u k , а в случае знака , искусственную переменную u k надо отнять от правой части основных ограничений).

Существуют ограничения не отрицательности переменных (если их нет для некоторой переменной х k , то их можно ввести путем замены всех вхождений этой переменной комбинацией x 1 k - х 2 k = х k , где х 1 k и х 2 k ). При этом для решения задачи линейного программирования необходимо иметь базис , т.е. набор переменных х i , в количестве, равным числу основных ограничений, причем каждая из этих переменных должна входить лишь в одно основное ограничение с множителем а ij = 1 . При отсутствии таких переменных их необходимо искусственно добавить в основные ограничения и снабдить индексами х m+1 , x m+2 и т.д. При этом считается, что переменные удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи не изменяется, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод ) .

При нахождении решения задачи линейного программирования (по варианту простого симплекс-метода ) применяют алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оценок. Они дают возможность делать переходы от одного шага к другому, а также показывают, когда итерационный процесс остановится и будет получен результат.

Первая оценка – это дельта-оценка , для переменной х j она имеет вид:

 

(1.4)

  Здесь выражение i B означает, что в качестве коэффициентов целевой функции, представленных в сумме выражения (1.4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Переменными а ij являются множители матрицы коэффициентов А при основных ограничениях, рассчитанные на данном шаге итерационного процесса. Дельта-оценки рассчитываются по всем переменным х i , имеющимся в задаче. Дельта-оценки для базисных переменных равны нулю.

После нахождения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка, и соответствующая ей переменная х k будет вводиться в базис.

Другой важной оценкой является тетта-оценка , следующего вида : (1.5)

По номеру k, найденному по дельта-оценке, мы получаем выход на переменную х k и элементы столбца Х B делим на соответствующие (только положительные) элементы столбца матрицы А, соответствующего переменой x k . Из полученных результатов выбираем минимальный, он и будет тетта-оценкой. а i -й элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выводиться из базиса, заменяясь элементом x k , полученным по дельта-оценке. Для осуществления такой замены нужно в i-ю строку k- гo столбца матрицы А поставить единицу, а остальные элементы k- го столбца заменить нулями. Подобное преобразование является одним шагом итерационного процесса.

Используем метод Гаусса для поведения преобразования. В соответствии с ним i-я строка всей матрицы А, а также i-я координата Х B делятся на a ik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата Х B умножаются на элемент ( 1k ). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также Х B 1 , и ( 1k ) B i . Для всех остальных строк кроме i-ой (базисной) строки производятся аналогичных действия. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех остальных его строках находятся 0. Так осуществляется один шаг итерационного алгоритма. Пошаговое выполнение алгоритма симплекс-метода продолжается до тех пор, пока не будет получен один из следующих результатов:


Все небазисные дельта-оценки больше нуля . Решение задачи линейного программирования представляет вектор с компонентами х, значения которых либо равны нулю, либо равны элементам столбца Х. Компоненты вектора стоят на базисных местах (например, если базис образуют переменные х 2 , x 4 , х 5 , то ненулевые компоненты стоят в векторе решения задачи линейного программирования на 2-м, 4-м и 5-м местах).

Имеются небазисные дельта-оценки, равные нулю . Задача линейного программирования имеет бесчисленное множество решений, представляемое лучом или отрезком.

Возможен вариант получения столбца отрицательных элементов на отрицательной рассчитанной дельта-оценке. В такой ситуации вычислить тетта-оценки невозможно, и необходимо сделать вывод, что система ограничений задачи линейного программирования несовместна, и у задачи линейного программирования нет решения.

Единственное решение задачи линейного программирования следует записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функции в точке решения L*(Х*). В других случаях необходимо словесно описать полученный результат. Если решение задачи линейного программирования не будет получено в течение 10–12 итераций симплекс-метода, то необходимо сделать вывод, что решение отсутствует в связи с неограниченностью функции цели.

При практическом решении задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 1.1):

Таблица 1.1

B

C B

X B

A 1

A n

Q

Базисные

Целевые

Правые

 

 

 

 

компоненты

Коэффиц.

Части

 

 

 

 

 

Базиса

ограничен

 

 

 

 

D

 

 

D1

 

D n

 

 

  Задание

Решить задачу линейного программирования.

L(x) = x 1 – 2x 2 + 3x 3

x 1 – 3x 2 3

2x 1 – x 2 + x 3 3

-x 1 + 2x 2 – 5x 3 3

Все x i 0 i = 1, …3

1. Вначале сведем задачу к каноническому виду

L(x) = x 1 – 2x 2 + 3x 3

x 1 – 3x 2 + x 4 = 3

2x 1 – x 2 + x 3 + x 5 = 3

-x 1 + 2x 2 – 5x 3 + x 6 = 3

Все x i 0 i = 1, …6

2. Составим таблицу симплекс-метода (табл. 1.2)

В данном случае базис образуют компоненты x 4 , x 5 , x 6 .

B

C B

X B

A 1

A 2

A 3

A 4

A 5

A 6

Q

A 4

0

3

1

-3

0

1

0

0

-

A 5

0

3

2

-1

1

0

1

0

3

A 6

0

3

-1

2

-5

0

0

1

-

D

 

 

-1

2

-3

0

0

0

 

A 4

0

3

1

-3

0

1

0

0

 

A 3

3

3

2

-1

1

0

1

0

 

A 6

0

3

-1

2

0

0

0

1

 

D

 

9

5

2

0

0

3

0

 

После вычисления дельта-оценок можно сделать вывод.

Данная задача будет иметь единственное решение, т.к. все небазисные дельта-оценки положительны.

3. Решение задачи будет выглядеть следующим образом

X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.